/**
 * 
 */
package string.passed2;

import java.util.Stack;

/**
 * @author xyyi
 *
 */
public class ValidParentheses {

	/**
		Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
		
		The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
	*/
    public boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        for (char bracket : s.toCharArray()) {
            if (isLeft(bracket)) {
                stack.push(bracket);
            }
            else {
            	if (stack.isEmpty() || !isPair(stack.pop(), bracket)) {
            		return false;
            	}
            }
        }
        
        return stack.isEmpty();
    }
	
	public boolean isValid(String s) {

		Stack<Character> stack = new Stack<Character>();

		for (char c : s.toCharArray()) {
			if (isLeft(c))
				stack.push(c);
			else {
				if (stack.isEmpty())
					return false;
				if (!isPair(stack.pop(), c)) {
					return false;
				}
			}
		}

		return stack.isEmpty();
	}

	private int currIndex = 1;

	public boolean isValidRecursive(String s, int level) {
		return false;
	}

	private boolean isLeft(char c) {
		return c == '(' || c == '[' || c == '{';
	}

	private boolean isPair(char c1, char c2) {
		return c1 == '(' && c2 == ')' ||
			   c1 == '[' && c2 == ']' ||
			   c1 == '{' && c2 == '}';
	}

	/**
	 * 
	 */
	public ValidParentheses() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
